// 归并排序的简化版本,主要简化了MergeSort函数的递归部分;升序;
#include <iostream>
#include <vector>
using namespace std;

void Merge(vector<int>& nums,int left,int mid,int right){
    // vector 数组要想引用的话,得明确加上&;

    int i,j,k;
    int length=right-left+1;
    int *temp=new int[length];
    for (j = mid + 1, k = 0,i=left; i <= mid && j <= right; k++)
    // j 用于遍历第二个有序的序列;用 left 遍历第一个有序序列;k 用于指向待存放的source_nums的位置
    {
        if (nums[i - 1] < nums[j - 1]) // 注意这里需要减一才是数组的下标
        {
            temp[k] = nums[i - 1];
            i++;
        }
        else
        {
            temp[k] = nums[j - 1];
            j++;
        }
    }
    if (i <= mid)
    {
        // 第一个序列还没有遍历完
        for (; i <= mid; i++)
        {
            temp[k] = nums[i - 1];
            k++;
        }
    }
    if (j <= right)
    {
        // 第二个序列还没有遍历完
        for (; j <= right; j++)
        {
            temp[k] = nums[j - 1];
            k++;
        }
    }
    // 将合并之后的有序序列放到 nums 数组中
    for (int i = 0; i < length; i++)
    {
        nums[left-1+i]=temp[i];
    }
    delete []temp; // 释放掉临时数组空间
    
}

void MergeSort(vector<int> &nums, int left, int right)
{
    if (left == right)
    {
        // 当拆分到最后只剩一个元素时,这个元素就是单独一组;
        return;
    }
    int mid;
    mid = (left + right) / 2;

    MergeSort(nums, left, mid);
    MergeSort(nums, mid + 1, right);
    Merge(nums, left, mid, right);
    return;
}

int main(){
    vector<int> nums = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    MergeSort(nums,1,nums.size());

    for (int i = 0; i < nums.size(); i++)
    {
        cout<<nums[i]<<",";
    }
    cout<<endl;
    return 0;
}